Parameterized Extension Complexity of Independent Set and Related Problems

摘要

Let $G$ be a graph on $n$ vertices and $\mathrm{STAB}_k(G)$ be the convexhull of characteristic vectors of its independent sets of size at most $k$. Westudy extension complexity of $\mathrm{STAB}_k(G)$ with respect to a fixedparameter $k$ (analogously to, e.g., parameterized computational complexity ofproblems). We show that for graphs $G$ from a class of bounded expansion itholds that $\mathrm{xc}(\mathrm{STAB}_k(G))\leqslant \mathcal{O}(f(k)\cdot n)$where the function $f$ depends only on the class. This result can be extendedin a simple way to a wide range of similarly defined graph polytopes. In caseof general graphs we show that there is {\em no function $f$} such that, forall values of the parameter $k$ and for all graphs on $n$ vertices, theextension complexity of $\mathrm{STAB}_k(G)$ is at most $f(k)\cdotn^{\mathcal{O}(1)}.$ While such results are not surprising since it is knownthat optimizing over $\mathrm{STAB}_k(G)$ is $FPT$ for graphs of boundedexpansion and $W[1]$-hard in general, they are also not trivial and in bothcases stronger than the corresponding computational complexity results.